package leetcode;

import java.util.Arrays;

/**
 * 排序算法
 *
 * @author 王霄
 * @date 2021/8/28 13:36
 */
public class SortDemo {
    public static void main(String[] args) {
        int[] arr1 = {3, 4, 1, 2, 7, 6, 9, 8, 5};
        int[] arr2 = {3, 4, 1, 2, 7, 6, 9, 8, 5};
        int[] arr3 = {3, 4, 1, 2, 7, 6, 9, 8, 5};
        System.out.println(Arrays.toString(bubbleSort(arr1)));
        System.out.println(Arrays.toString(selectionSort(arr2)));
        System.out.println(Arrays.toString(quickSort(arr3)));
    }

    /**
     * 冒泡排序
     *
     * <p>
     * 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
     * 针对所有的元素重复以上的步骤，除了最后一个；
     * 重复步骤1~3，直到排序完成。
     * <\p>
     */
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序
     *
     * <p>
     * 它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
     * 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
     * <\p>
     */
    public static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
        return arr;
    }


    /**
     * 快速排序
     * <p>
     * 通过一趟排序将要排序的数据分割成独立的两部分，
     * 其中一部分的所有数据比另一部分的所有数据要小，
     * 再按这种方法对这两部分数据分别进行快速排序，
     * 整个排序过程可以递归进行，使整个数据变成有序序列
     * <\p>
     */
    public static int[] quickSort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }

    public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int index = left + 1;
            for (int i = index; i <= right; i++) {
                if (arr[i] < arr[left]) {
                    int temp = arr[i];
                    arr[i] = arr[index];
                    arr[index] = temp;
                    index++;
                }
            }
            index--;
            int temp = arr[left];
            arr[left] = arr[index];
            arr[index] = temp;
            quickSort(arr, left, index - 1);
            quickSort(arr, index + 1, right);
        }
        return arr;
    }
}
